\contentsline {section}{\numberline {1}数据结构}{2}{section.1}%
\contentsline {subsection}{\numberline {1.1}并查集}{2}{subsection.1.1}%
\contentsline {subsection}{\numberline {1.2}对顶堆}{5}{subsection.1.2}%
\contentsline {subsection}{\numberline {1.3}线段树}{6}{subsection.1.3}%
\contentsline {subsubsection}{\numberline {1.3.1}线段树1}{6}{subsubsection.1.3.1}%
\contentsline {subsubsection}{\numberline {1.3.2}线段树2}{8}{subsubsection.1.3.2}%
\contentsline {subsubsection}{\numberline {1.3.3}线段树3}{10}{subsubsection.1.3.3}%
\contentsline {subsection}{\numberline {1.4}树状数组}{14}{subsection.1.4}%
\contentsline {subsection}{\numberline {1.5}块状数据结构}{14}{subsection.1.5}%
\contentsline {subsubsection}{\numberline {1.5.1}分块}{14}{subsubsection.1.5.1}%
\contentsline {subsection}{\numberline {1.6}可持久化数据结构}{17}{subsection.1.6}%
\contentsline {subsubsection}{\numberline {1.6.1}可持久化线段树}{17}{subsubsection.1.6.1}%
\contentsline {subsubsection}{\numberline {1.6.2}第k小数}{19}{subsubsection.1.6.2}%
\contentsline {subsection}{\numberline {1.7}ac自动机}{20}{subsection.1.7}%
\contentsline {section}{\numberline {2}数论}{22}{section.2}%
\contentsline {subsection}{\numberline {2.1}Numbertheory}{22}{subsection.2.1}%
\contentsline {subsection}{\numberline {2.2}组合数学}{22}{subsection.2.2}%
\contentsline {subsection}{\numberline {2.3}逆元}{23}{subsection.2.3}%
\contentsline {subsection}{\numberline {2.4}快速幂}{24}{subsection.2.4}%
\contentsline {subsection}{\numberline {2.5}质数}{25}{subsection.2.5}%
\contentsline {subsection}{\numberline {2.6}约数}{26}{subsection.2.6}%
\contentsline {subsection}{\numberline {2.7}卢卡斯定理}{27}{subsection.2.7}%
\contentsline {subsection}{\numberline {2.8}斯特林数}{28}{subsection.2.8}%
\contentsline {subsection}{\numberline {2.9}整除}{28}{subsection.2.9}%
\contentsline {section}{\numberline {3}基础算法}{28}{section.3}%
\contentsline {subsection}{\numberline {3.1}二分}{28}{subsection.3.1}%
\contentsline {subsection}{\numberline {3.2}三分}{29}{subsection.3.2}%
\contentsline {subsection}{\numberline {3.3}位运算}{30}{subsection.3.3}%
\contentsline {subsection}{\numberline {3.4}离散化}{30}{subsection.3.4}%
\contentsline {subsection}{\numberline {3.5}前缀和}{32}{subsection.3.5}%
\contentsline {subsection}{\numberline {3.6}差分}{32}{subsection.3.6}%
\contentsline {subsection}{\numberline {3.7}st}{34}{subsection.3.7}%
\contentsline {subsection}{\numberline {3.8}倍增}{34}{subsection.3.8}%
\contentsline {subsection}{\numberline {3.9}高精度}{35}{subsection.3.9}%
\contentsline {subsection}{\numberline {3.10}双指针}{36}{subsection.3.10}%
\contentsline {subsection}{\numberline {3.11}区间合并}{36}{subsection.3.11}%
\contentsline {section}{\numberline {4}动态规划}{37}{section.4}%
\contentsline {subsection}{\numberline {4.1}背包}{37}{subsection.4.1}%
\contentsline {subsection}{\numberline {4.2}区间dp}{39}{subsection.4.2}%
\contentsline {subsection}{\numberline {4.3}线性dp}{40}{subsection.4.3}%
\contentsline {subsection}{\numberline {4.4}单调队列优化dp}{42}{subsection.4.4}%
\contentsline {section}{\numberline {5}解题思路}{42}{section.5}%
\contentsline {subsection}{\numberline {5.1}解题}{42}{subsection.5.1}%
\contentsline {subsection}{\numberline {5.2}分数规划}{46}{subsection.5.2}%
\contentsline {section}{\numberline {6}常用函数}{46}{section.6}%
\contentsline {subsection}{\numberline {6.1}常用函数1}{46}{subsection.6.1}%
\contentsline {section}{\numberline {7}字符串}{48}{section.7}%
\contentsline {subsection}{\numberline {7.1}字符串哈希}{48}{subsection.7.1}%
\contentsline {subsection}{\numberline {7.2}tire字典树}{49}{subsection.7.2}%
\contentsline {section}{\numberline {8}图论}{51}{section.8}%
\contentsline {subsection}{\numberline {8.1}最短路}{51}{subsection.8.1}%
\contentsline {subsubsection}{\numberline {8.1.1}Dijkstra}{51}{subsubsection.8.1.1}%
\contentsline {subsubsection}{\numberline {8.1.2}Floyd}{52}{subsubsection.8.1.2}%
\contentsline {subsection}{\numberline {8.2}最小生成树}{53}{subsection.8.2}%
\contentsline {subsubsection}{\numberline {8.2.1}Kruskal}{53}{subsubsection.8.2.1}%
\contentsline {subsubsection}{\numberline {8.2.2}Prim}{54}{subsubsection.8.2.2}%
\contentsline {subsection}{\numberline {8.3}无向图三元环计数}{55}{subsection.8.3}%
\contentsline {subsection}{\numberline {8.4}结论}{57}{subsection.8.4}%
\contentsline {subsection}{\numberline {8.5}拓扑排序}{57}{subsection.8.5}%
\contentsline {subsection}{\numberline {8.6}负环}{58}{subsection.8.6}%
\contentsline {subsection}{\numberline {8.7}tarjan强连通分量}{59}{subsection.8.7}%
\contentsline {subsection}{\numberline {8.8}lca}{60}{subsection.8.8}%
